#include <stdio.h>
#include <stdlib.h>

typedef struct block_item_{
    int max_value;
    int start_index;
} block_item_t;

typedef struct block_list_ {
    block_item_t block_item;
    struct block_list_ *next;
} block_list_t;

block_list_t  *devide_array_to_block(int *arr, int arr_size, int block_size) 
{
    block_list_t *block_list = NULL;
    int i = 0;
    int count = 0;
    int block_index = 0;
    int is_need_add = 0;
    int max_value = 0;

    if (arr_size <= 0 || block_size <= 1) {
        printf("Invalid array size %d, block size %d\n", arr_size, block_size);
        return NULL;
    }

    printf("Array size %d, block size %d\n", arr_size, block_size);

    if (arr_size < block_size) {
        block_list = (block_list_t *)malloc(sizeof(block_list_t));
        block_list->next = NULL;
        block_list->block_item.max_value = arr[0];
        block_list->block_item.start_index = 0;
        for (i =1; i < arr_size; i++) {
            if (arr[i] > block_list->block_item.max_value) {
                block_list->block_item.max_value = arr[i];
            }
        }
        return block_list;
    }

    /* TODO : devide array to block list*/
    
}


int find_max_value_in_block(block_list_t *block_list, int *arry, int arr_size, int goal_index)
{
    int index = -1;
    block_list_t *block = block_list;
    int search_begin_index = 0;
    int search_end_index = 0;
    int i = 0;

    while (block) {
        if (block->block_item.max_value >= goal_index) {
            search_begin_index =block->block_item.start_index;
            if (block->next) {
                search_end_index = block->next->block_item.start_index;
                break;
            }
         } else {
           block = block->next;
         }
    }

    printf("search begin index %d, search end index %d\n", search_begin_index, search_end_index);
    if (search_begin_index ==0 || search_end_index ==0) {
        return index;
    }

    for( i = search_begin_index; i < search_end_index; i++) {
        if(arry[i] == goal_index) {
            index = i;
            break;
        }
    }

    return index;
}

void construct_block_list_node(block_list_t *list, int max_value, int start_index)
{
    list->block_item.max_value = max_value;
    list->block_item.start_index = start_index;
    list->next = NULL;
}

void free_block_list(block_list_t *block_list)
{
    block_list_t *tmp = NULL;
    while (block_list) {
        tmp = block_list;
        block_list = block_list->next;
        free(tmp);
    }
}
int main(void) {
    int arr[] = {8 ,17 ,5 ,12 ,25 ,35 ,22 ,31 ,39 ,51 ,42  ,48 };
    block_list_t *block_list = NULL;
    block_list_t *head = NULL;
    int is_init_block_list = 0;
    int index = 0;

    do {
        head = malloc(sizeof(block_list_t));
        if (head == NULL) {
            printf("malloc block_list failed\n");
            break;
        }

        block_list = head;
        construct_block_list_node(block_list, arr[1], 0);
        
        block_list->next = malloc(sizeof(block_list_t));
        if (block_list->next == NULL) {
            printf("malloc block_list failed\n");
            break;
        }
        block_list = block_list->next;
        construct_block_list_node(block_list, arr[5], 4);

        block_list->next = malloc(sizeof(block_list_t));
        if (block_list->next == NULL) {
            printf("malloc block_list failed\n");
            break;
        }
        block_list = block_list->next;
        construct_block_list_node(block_list, arr[9], 9);
        is_init_block_list = 1;
    } while(0);
   
    if (is_init_block_list == 1) {
        printf("init block list success!\n");

        index = find_max_value_in_block(head, arr, 12, 22);
        printf("find index %d\n", index);
    }

    if (head) {
        free_block_list(head);
    }
    
    return 0;
}